/**
 * 删除并获得点数
 * https://leetcode.cn/problems/delete-and-earn/description/
 */

class Solution1 {
    public int deleteAndEarn(int[] nums) {

        //预处理
        int n = 10001;
        int[] arr = new int[n];

        for(int x : nums) arr[x] += x;

        ////1.创建dp表
        int[] f = new int[n];
        int[] g = new int[n];

        //2.初始化
        f[0] = arr[0];


        //3.填表
        for(int i = 1;i < n;i++){
            f[i] = g[i-1] + arr[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }

        //4.返回
        return Math.max(f[n-1],g[n-1]);
    }
}

/**
 * 粉刷房子
 * https://leetcode.cn/problems/JEj789/description/
 */
class Solution2 {
    public int minCost(int[][] costs) {
        int m = costs.length;

        int[][] dp = new int[m][3];

        //初始化
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];

        //填表
        for(int i = 1;i < m;i++){
            dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2]) + costs[i][0];
            dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2]) + costs[i][1];
            dp[i][2] = Math.min(dp[i-1][1],dp[i-1][0]) + costs[i][2];
        }

        return dp[m-1][0] > dp[m-1][1] ? Math.min(dp[m-1][1],dp[m-1][2]) : Math.min(dp[m-1][0],dp[m-1][2]);
    }
}
/**
 * 买卖股票的最佳时机（含冷冻期）
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
 */
class Solution3 {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int[][] dp = new int[n][3];

        //初始化
        dp[0][0] = -prices[0];

        for(int i = 1;i < n;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][0] + prices[i],dp[i-1][1]);
            dp[i][2] = dp[i-1][1];
        }

        return Math.max(dp[n-1][1],dp[n-1][2]);
    }
}